1. Technical Field
The invention relates to the storage and playback of digitized video segments on a display device of a digital computer, and more particularly relates to a system and a method of data compression and decompression that supports real-time recovery and reconstruction, with both forward and reverse playback, of the digitized video segment on a minimal personal computer system. Still more particularly, the invention relates to a software-based method for real-time video decompression and playback with a computational load readily carried by the central processing unit (CPU) of low-end personal computers (e.g. a computer based upon an Intel 80386SX microprocessor running at 16 MHz).
2. Description of the Related Art
A video signal is a sequence of images or frames, which when displayed in sequence at a given frame rate (e.g., 15 to 30 frames-per-second in a personal computer), simulates the appearance of motion to a human observer. In a personal computer system, each frame of the digitized video is an array of picture elements or "pixels", which are the minimum unit for assignment of color and intensity information. A frame may have in excess of half a million pixels. If full frames were replaced at the frame rate in excess of 15 frames-per-second, a computer would be required to recover from storage and write to video memory several million pixels each second. Few contemporary auxiliary data storage devices have both the bandwidth required to pass such quantities of data and the storage capacity to hold more than a few full frames of digital video information. As used here, bandwidth means the volume of data per unit time which can be recovered from an auxiliary storage device.
Data compression is used to accommodate auxiliary storage devices in the storage and recovery of digitized video segments for playback in real time. Data compression is based on eliminating redundant information from the frames of a digital video segment. The idea is to convey only that information which changes from frame to frame. Consider an image of a person standing unmoving against a constant or near constant background, such as the sky. As long as the person remained still, the information changing from frame to frame would be minimal. A perfect data compression technique would reduce the data stored for each frame to little more than a place holder for each frame indicating the passage of time. As the person began to speak, information indicating that the pixels in the location around the person's mouth are changing from frame to frame can be specified. Such a video compression technique is a type of frame differencing video compression, which is designed to pass only information relating to particular pixel locations which differ from one frame to the next.
A frame compressed by a frame-differencing process has consisted of two separate entities. One is a mechanism to denote the addresses (or locations) in the frame of the pixels that differed from the previous frame. The second entity is the values of the pixels that changed (i.e., the new information). A binary bit map is used to mark the pixels of a frame which differed from the previous frame. Such a map would be an M.times.N array of "1's" and "0's" corresponding to the M.times.N array of pixels in a frame. The values of the pixels which change follow in a sequential list.
To generate a bit map, corresponding pixel locations in each frame are compared to determine if a change took place. If an 8 bit value (usually called one byte) is used to represent the color value of each pixel that changed, considerable reduction of the data over a full frame is attained. If two or three bytes are used to represent the color value of the uncompressed digital video data, the amount of attained compression is commensurately larger. Where the number of changed pixels within each frame remains small, substantial savings in storage space and reduction in bandwidth demands are achieved.
Data so compressed reduces the amount of storage space required, allowing compressed digital video data to be stored in storage devices that have low sustained read rates (i.e., bandwidth) like compact disk read only memory (CD-ROM) and read/write (R/W) optical storage devices, and alleviate the CPU burden of reading the video data from storage and writing it to the video buffer of display devices such as the Extended Graphics Array (XGA) and super video graphics adaptor (SVGA) that drive display monitors. Frame-differencing video compression processes can be implemented in low-end personal computers with addition of programming, only because they offer a reasonable amount of data compression while simultaneously providing a data format of low computational complexity for real-time decompression and display.
Frame-differencing techniques require a processor to decompress compressed digital video information and to rewrite the changed portions of the frame to the video buffer. In low-end personal computers this processor will be the system central processing unit (CPU). Frame-differencing techniques relieve the CPU of the burden of rewriting of the entire video buffer every one fifteenth of a second, which otherwise can overload microprocessors such as an Intel 80386SX running at 16 Mhz.
Frame-differencing processes that can decompress a compressed video stream with low computational complexity code the information which differs from one frame to the next and inherently provide a forward direction of playback. A video segment replayed by updating the video buffer of the display device with only the information in a frame that is different from the previous frame does not provide for recovering and reconstruction of frames earlier in time. Reverse playback with frame-differencing methods of low computational complexity in decompression have not been done because the earlier frames cannot be reconstructed from the compressed video stream.
Providing a frame-differencing process for digital video compression which also permits reverse playback without requiring additional data storage capacity and without adding to the computational complexity of the decompression process would represent improved capability and is desirable.